package Algorithm.String;

import java.util.*;

//https://leetcode-cn.com/problems/concatenated-words/
//472. 连接词
public class Leetcode472_notice_连接词 {

    /**
     * 序列DP+字符串Hash
     */
    class Solution {
        Set<Long> set;
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            set = new HashSet<Long>();
            long offset = 131;
            long h = 31;
            for(String s : words){
                long hashCode = 0;
                for(char c : s.toCharArray()){
                    hashCode = h * hashCode + (c -'a') + offset;
                }
                set.add(hashCode);
            }
            List<String> result = new ArrayList<String>();
            for(String s : words){
                if(check(s)){
                    result.add(s);
                }
            }

            return result;
        }

        public boolean check(String s){
            int[] dp = new int[s.length() + 1];
            long h = 31;
            long offset = 131;
            Arrays.fill(dp, -1);
            dp[0] = 0;

            for(int i=0;i<s.length()+1;i++){
                if(dp[i]==-1){
                    continue;
                }
                long cur = 0;
                for(int j=i+1;j<s.length()+1;j++){
                    cur = cur * h + (s.charAt(j-1) - 'a') + offset;
                    if(set.contains(cur)){
                        dp[j] = Math.max(dp[j], dp[i]+1);
                    }
                }
            }

            if(dp[s.length()]>1){
                return true;
            }

            return false;
        }
    }
}
